# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

root=TreeNode(4)
root.left=TreeNode(2)
root.right=TreeNode(7)
root.left.left=TreeNode(1)
root.left.right=TreeNode(3)
root.right.left=TreeNode(6)
root.right.right=TreeNode(9)

def invertTree(root: TreeNode) -> TreeNode:
    if root:
        dfs(root)
    return root

def dfs(root):
    #出口条件，叶子节点
    if root.left==None and root.right==None:
        return None
    if root.left and root.right:
        #先进行深度递归
        dfs(root.left)
        dfs(root.right)
        #交换节点
        temp=root.left
        root.left=root.right
        root.right=temp
    if root.left and root.right==None:
        dfs(root.left)
    if root.right and root.left==None:
        dfs(root.right)
